/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._921;

import java.util.Stack;

/**
 *
 * 给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。
 *
 * 从形式上讲，只有满足下面几点之一，括号字符串才是有效的：
 *
 * 它是一个空字符串，或者
 * 它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
 * 它可以被写作 (A)，其中 A 是有效字符串。
 * 给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。
 *
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._921
 * @ClassName: MinAddToMakeValid
 * @Author: linyaonan
 * @Date: 2020/3/26 17:24
 */
public class MinAddToMakeValid {

    public int minAddToMakeValid(String S) {
        Stack<Character> stack = new Stack<>();
        if (S == null || S.length() == 0) {
            return 0;
        }

        for (char c : S.toCharArray()) {
            if (c == '(') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    stack.push(c);
                } else {
                    Character peek = stack.peek();
                    if (peek == '(') {
                        stack.pop();
                    } else {
                        stack.push(c);
                    }
                }
            }
        }

        return stack.size();
    }

}
